package leetCode.solution;

import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.stream.Stream;

import com.alibaba.fastjson.JSON;

public class Solution347 {
	
	public static void main(String[] args) {
		System.out.println(JSON.toJSONString(new Solution347().topKFrequent(new int[] {1,1,1,1,1,3,4,5,5,5,5,6,7,2,3,9,9,9,6}, 3)));
	}

	public int[] topKFrequent(int[] nums, int k) {
		int arr[] = new int[k];
		PriorityQueue<java.util.Map.Entry<Integer, Integer>> queue = new PriorityQueue<java.util.Map.Entry<Integer, Integer>>(new Comparator<java.util.Map.Entry<Integer, Integer>>() {
			@Override
            public int compare(java.util.Map.Entry<Integer, Integer> o1, java.util.Map.Entry<Integer, Integer> o2) {
                return o1.getValue() - o2.getValue();
            }
		});
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		for(int i = 0;i<nums.length;i++) {
			map.compute(nums[i], (t,v)->v=v==null?1:v+1);
		}
		
		for(java.util.Map.Entry<Integer, Integer> entry : map.entrySet()) {
			if(queue.size()==k) {
				if(queue.peek().getValue()<entry.getValue()) {
					queue.poll();
					queue.offer(entry);
				}
			}else {
				queue.offer(entry);
			}
		}
		
		Stream.iterate(0, i -> i + 1).limit(k).forEach(i -> {
			arr[i]=queue.poll().getKey();
		});
//		for(int i=0;i<k;i++) {
//			arr[i]=queue.poll().getKey();
//		}
		
		return arr;
    }
}
